package MiddlePractice;

import java.util.LinkedList;
import java.util.List;

import org.junit.Test;

public class Demo17 {
//	17. 电话号码的字母组合
//	给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
//
//	给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

	
	private String[] digitMap = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
	private List<String> ans = new LinkedList<>();
	
	public List<String> letterCombinations(String digits) {
		if(digits.length() == 0) {
			return new LinkedList<String>();
		}
		
		char[] charArr = digits.toCharArray();
		int[] nums = new int[charArr.length];
		
		for(int i=0; i<charArr.length; i++) {
			nums[i] = charArr[i] - 48;
		}
		
		backTrace(nums, new LinkedList<Character>(), charArr.length, 0);
		return ans;
    }
	
	private void backTrace(int[] num, LinkedList<Character> trace, int maxLen, int i) {
		if(trace.size() == maxLen) {
			StringBuffer sb = new StringBuffer();
			for(char c : trace) {
				sb.append(c);
			}
			ans.add(sb.toString());
			return;
		}
		
		char[] charArr = digitMap[num[i]].toCharArray();
		
		for(char c : charArr) {
			if(trace.indexOf(c+"") != -1) {
				//路径已包含这个字符   不选择 (剪枝)
				continue;
			}
			trace.addLast(c);
			//去下个数字找
			backTrace(num, trace, maxLen, i+1);
			//撤销本次选择  重新选新路径
			trace.removeLast();
		}
		
		
	}
	
	@Test
	public void test_17() {
		List<String> ans = letterCombinations("2345");
		for(String s : ans) {
			System.out.print(s + ",");
		}
	}
}
